<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <title>Title</title>
  </head>
  <body>
    <script>
      /*  718. 最长重复子数组
      给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。
  示例：

  输入：
  A:           [1,2,3,2,1]
  B:           [3,2,1,4,7]
      输出：3
      解释：
      
  长度最长的公共子数组是 [3, 2, 1] */

      //动态规划

      const findLength = (A, B) => {
        const m = A.length;
        const n = B.length;
        const dp = new Array(m + 1);
        for (let i = 0; i <= m; i++) {
          // 初始化整个dp矩阵，每个值为0
          dp[i] = new Array(n + 1).fill(0);
        }

        let res = 0;
        // i=0或j=0的base case，初始化时已经包括
        for (let i = 1; i <= m; i++) {
          // 从1开始遍历
          for (let j = 1; j <= n; j++) {
            // 从1开始遍历
            if (A[i - 1] == B[j - 1]) {
              dp[i][j] = dp[i - 1][j - 1] + 1;
            } // A[i-1]!=B[j-1]的情况，初始化时已包括了
            res = Math.max(dp[i][j], res);
          }
        }
        return res;
      };

      // 降纬 变成一维数组
      // [1,2,3,2,1]
      //  [3,2,1,4,7]
      var findLength2 = function (nums1, nums2) {
        const m = nums1.length;
        const n = nums2.length;
        let res = 0;
        const dp = new Array(n + 1).fill(0);

        for (let i = 1; i <= m; i++) {
          for (let j = n; j >= 1; j--) {
            if (nums1[i - 1] == nums2[j - 1]) {
              dp[j] = dp[j - 1] + 1;
            } else {
              dp[j] = 0;
            }
            res = Math.max(dp[j], res);
          }
        }
        return res;
      };
   //  题解  https://leetcode-cn.com/problems/maximum-length-of-repeated-subarray/solution/zhe-yao-jie-shi-ken-ding-jiu-dong-liao-by-hyj8/

      // 滑动窗口
      const arr1 = [1, 2, 3, 2, 1];
      const arr2 = [3, 2, 1, 4, 7];
      console.log(findLength2(arr1, arr2));
      consoel.log("ssss")
    </script>
  </body>
</html>
